1. Technical Field
The present invention relates to methods and systems for identifying objects in an image, and in particular, to methods and systems for identifying lines, curves or similar shapes in an image or graphical representation of a dataset.
2. Description of the Related Art
There are many applications for machine vision and analysis in which it is useful to find the location of lines, curves or similar shapes in an image. For example, WO 99/08233 describes a large number of different types of analyses which can be conducted on assay well plates, gels and blots used in chemical, biochemical and physiological analyses. In such a use, it is helpful to be able to identify the position of the rows and columns of the sample grids on the plates, gels and blots.
Similarly, there are many manufactured products which include arrays, cross hatching or other regular patterns, such as printed or micro-replicated materials, and chip sockets. Machine vision is a useful way of inspecting such products, but, again, there often must be some ability to determine the orientation and position of the shapes in the image for this to be useful.
Many tests also vary with time, and it is important to be able to track the location of specific peaks or bands in the data as they move over time. For example, a graph showing the time variability in the strength of signal at particular wavelengths for nuclear magnetic resonance (NR) or infrared (IR) peak data sometimes will drift, and it is desirable to accurately identify the different peaks even as they shift around.
Still further, recent approaches to data mining and knowledge engineering seek out unrecognized patterns in data. For any data which can be represented graphically, finding lines, curves or other shapes in the resulting image can be a way to identify hidden patterns.
The present invention addresses these problems through a new technique called xe2x80x9ccentroid integrationxe2x80x9d.
Centroid integration starts by obtaining an image or other graphical representation of the data to be analyzed, and digitizing the image into pixels. Using any suitable algorithm, individual features in the image are identified. The centroid position of each feature, and characteristic values of each feature all are determined. These are used to produce a xe2x80x9ccollapsed image,xe2x80x9d where each feature is represented by a point object at the centroid location, with the point object having values corresponding to the characteristic values. Any value appropriate to the application may be used as a characteristic value. For example, the area of the feature and the integrated intensity of the feature over its entire area would be typical characteristic values.
The detail level of the collapsed image can be controlled by using appropriate algorithms to distinguish between different features. Alternatively, the manner in which a particular algorithm distinguishes between different features can be adjusted, e.g., by requiring more or less discrimination in a chosen value in adjacent pixels to qualify as the boundary of a particular feature.
Once the collapsed image is produced, an integration line is established at an appropriate location in the collapsed image, such as at one edge. This integration line is swept across at least the relevant portion of the collapsed image in steps. At each step, the sum of a characteristic value, e.g., the integrated intensity, of each centroid within a predetermined region on either side of the line is determined and recorded. The result is a two dimensional plot with a series of peaks, each peak corresponding to a feature (or a band of features, if the features happen to lie on the same integration line).
Note that this process is different from simply integrating the image intensity along the search line. Due to the use of a collapsed image, each feature effectively has its characteristic values concentrated at its centroid.
Centroid integration results in a set of very well defined peaks in the resulting line profile. Regular integration would result in a set of smeared out peaks and, in the case of an image with significant variation in the positions of the individual features, the result would often be unusable. As a result, centroid integration is much more tolerant of local variation in feature positions than conventional integration.
The size of the steps (or xe2x80x9csmoothing windowxe2x80x9d) by which the integration line is moved can be important in some settings. For example, if the image is expected to include regularly spaced lines, optimum results often can be obtained by setting a smoothing window that is proportional to the spacing of the lines. The use application of centroid integration to images containing lines or grids of features is discussed in more detail in a co-assigned U.S. patent application Ser. No. 09/422,535, filed Oct. 21, 1999, entitled, xe2x80x9cAutogrid Analisisxe2x80x9d, which is incorporated herein by reference.
If the characteristics of the data in the image are not known, and particularly if the objective is-to find hidden patterns in the data, it may be desirable to test a variety of smoothing window sizes to find one that maximizes the peak differentiation resulting from the centroid integration.
Similarly, the size of the predetermined region on either side of the integration line in which the characteristic values are summed may be varied. Typically, it will match the size of the smoothing window, but in some situations different sizes may be desirable. For example, it may be useful always to move the line in one pixel steps, but analyze the resulting data for different sized regions on either side of the integration line.
Centroid integration is not limited to integrating using straight lines or lines parallel to the sides of the image. Curves or other shapes can be used instead of a straight line to perform the integration, especially if the data is expected to be curved or if one is attempting to identify patterns in the image or data set matching the curve or other shape. It also often will be desirable to test the lines, curves or other shapes at a variety of orientations.
The image being analyzed can be virtually anything, ranging from a photograph of an object to a mathematical representation of a large dataset. In a photograph, the shape found by centroid integration will often be the actual shape of the object, but in a mathematical representation of a dataset, the shape may actually represent a pattern in the data.
Centroid integration also can be applied to higher dimensional analysis. In this situation, instead of moving a line or other one dimensional shape across a two-dimensional graph or image of data, a plane, hyperplane or other multi-dimensional shape is moved through a graph or other representation of data having one more dimension than the plane, hyperplane or other multi-dimensional shape. The characteristic values are summed to a particular point on the plane, hyperplane or other shape.
As will be apparent, centroid integration has a very wide range of potential applications to identify patterns and shapes.